/** @file
 * A linked list implementation in static memory
 *
 * Author: Ratish J. Punnoose
 * $Id:$
 */
#ifndef __LL_STATIC_H_
#define __LL_STATIC_H_


/* Author: Ratish J. Punnoose, 2006
 * This file is part of TiROS, the Tickless Real-Time Operating System.
 * Copyright(c) 2006, 2007: Ratish J. Punnoose.
 * Copyright(c) 2006 Sandia Corporation. Under the terms of Contract
 * DE-AC04-94AL85000 with Sandia Corporation, the U.S. Government retains
 * certain rights in this software. 
 * 
 * TiROS is free software; you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free
 * Software Foundation; either version 2 or (at your option) any later version.
 *
 * TiROS is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with TiROS; if not, write to the Free Software Foundation, Inc.,
 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
 *
 * As a special exception, if other files instantiate templates or use macros
 * or inline functions from this file, or you compile this file and link it
 * with other works to produce a work based on this file, this file does not
 * by itself cause the resulting work to be covered by the GNU General Public
 * License. However the source code for this file must still be made available
 * in accordance with section (3) of the GNU General Public License.
 *
 * This exception does not invalidate any other reasons why a work based on
 * this file might be covered by the GNU General Public License.
 *
 */


/** \name Linked_List
 * Static Memory Linked List Functions 
 * The linked list consists of two parts.
 * Part 1: The user data in an array of fixed-size user data elements.
 * This  is  not touched by these linked list functions. 
 * Part 2: The linked list metadata.  This is one byte per user-data
 * element.  Each byte is associated with the corresponding user-data
 * element and the content of this byte is the next index in the list.
 * @{ */
#ifndef LL_INLINE
#  define LL_INLINE static inline
#endif

/** A default value for the linked list index element type.  This can
 * be overridden by a user before including this file. The type has to
 * be an "unsigned   [char|short|int|long]" */
#ifndef LL_ELEM_TYPE
#  warning "using default type for LL"
#  define LL_ELEM_TYPE  unsigned char
#endif


typedef LL_ELEM_TYPE 	ll_ind_t;
typedef ll_ind_t  	ll_list_t;

#ifndef ILLEGAL_ELEM
#  define ILLEGAL_ELEM  ((ll_ind_t) (~0))
#endif




LL_INLINE     void LL_init( ll_ind_t metadata[], int num_array_elems);
LL_INLINE ll_ind_t LL_peek_head(ll_list_t *lst, 
				/*@unused@*/ ll_ind_t metadata[]);
LL_INLINE ll_ind_t LL_pop_head(ll_list_t *lst, ll_ind_t metadata[]);
LL_INLINE     void LL_add_head(ll_list_t *lst, ll_ind_t metadata[],
			   ll_ind_t elem);
LL_INLINE ll_ind_t LL_peek_tail(ll_list_t *lst, ll_ind_t metadata[]);
LL_INLINE     void LL_add_tail(ll_list_t *lst, ll_ind_t metadata[],  
			   ll_ind_t elem);

LL_INLINE ll_ind_t LL_remove_elem(ll_list_t *lst, ll_ind_t metadata[],  
				  ll_ind_t elem);
LL_INLINE ll_ind_t LL_next_elem(/*@unused@*/ll_list_t *lst, 
				ll_ind_t metadata[], 
				ll_ind_t curr_elem);


/** Prototype for a function that returns the relative priority
 *   between two elements in the list. 
 *
*/
typedef unsigned char (* prior_gt_t)(ll_ind_t newobj, ll_ind_t oldobj);

/** Add an element to the list in prioritized order.
 * @param lst The linked list.
 * @param metadata   Linked list metadata.
 * @param  elem   The element to be added.
 * @param pfunc   Pointer to a function of type prior_gt_t which when
 * called will return the relative ordering of the two elements.
 */
LL_INLINE void LL_add_prio(ll_list_t *lst, ll_ind_t metadata[],
			   ll_ind_t elem, const prior_gt_t pfunc);




/** Initialize the linked list
 * @param num_array_elems  The number of user data elements that this
 *                         list keeps track of.
 * @param metadata         This should be a pointer to memory of size
 *                         (sizeof (ll_ind_t) * num_array_elems
 */
LL_INLINE void LL_init( ll_ind_t metadata[], int num_array_elems)
{
	int i;
	for (i=0; i < num_array_elems; i++) {
		metadata[i] = ILLEGAL_ELEM;
	}
}




/** Peek at the head of the queue
 * @param lst   The linked list.
 * @param metadata  Metadata for the list. 
 * @return  The element at the head of the queue. */
LL_INLINE ll_ind_t LL_peek_head(ll_list_t *lst, 
				/*@unused@*/ ll_ind_t metadata[])
{
	(void)metadata; /* Not used */
	return *lst;
}



/** Pop the head of the queue
 * @param lst  The linked list.
 * @param metadata  Metadata for the list. 
 * @return The element at the head of the queue. */
LL_INLINE ll_ind_t LL_pop_head(ll_list_t *lst, ll_ind_t metadata[])
{
	ll_ind_t curr = *lst;
	if (curr != ILLEGAL_ELEM) {
		*lst = metadata[curr];  /* Point to next elem. */
		metadata[curr] = ILLEGAL_ELEM; /* Reinitialze this
						  element. */
	}
	return curr;
}



/** Add an element to the head of the queue.
 * @param lst  The linked list.
 * @param metadata Metadat for the list.
 * @param elem   The element to be added. */
LL_INLINE void LL_add_head(ll_list_t *lst, ll_ind_t metadata[],
			   ll_ind_t elem)
{
	ll_ind_t curr = *lst;
	*lst = elem;
	metadata[elem] = curr;
}




/** Peek at element at the tail of the queue.
 * @param lst  The linked list.
 * @param metadata Metadat for the list. */
LL_INLINE ll_ind_t LL_peek_tail(ll_list_t *lst, ll_ind_t metadata[])
{
	ll_ind_t tmp, curr = *lst;
	tmp = curr;
	while(curr != ILLEGAL_ELEM) {
		tmp = curr;
		curr = metadata[curr];
	}
	return tmp;
}




/** Add an element to the tail of the queue.
 * @param lst  The linked list.
 * @param metadata Metadat for the list.
 * @param elem   The element to be added. */
LL_INLINE void LL_add_tail(ll_list_t *lst, ll_ind_t metadata[],  
			   ll_ind_t elem)
{
	ll_ind_t tmp, curr = *lst;
	if (curr == ILLEGAL_ELEM) {
		*lst = elem;
	} else {
		do {
			tmp = curr;
			curr = metadata[curr];
		} while ( curr != ILLEGAL_ELEM) ;
		metadata[tmp] = elem;
	}
	metadata[elem] = ILLEGAL_ELEM;
}



/** Remove an element from the queue
 * @param lst The linked list.
 * @param metadata  Metadata for the list.
 * @param elem   The element to be removed.
 * @return  The element is returned if successful, else ILLEGAL_ELEM
 * is returned. */
LL_INLINE ll_ind_t LL_remove_elem(ll_list_t *lst, ll_ind_t metadata[],  
			   ll_ind_t elem)
{
	ll_ind_t tmp, curr = *lst;
	if (curr == ILLEGAL_ELEM) {
		goto quit;
	}
		
	if (curr == elem) {/* If item to be removed is at head */
		*lst = metadata[elem]; /* Set listhead to next. */
		/* Reinitialize current element. */
		metadata[elem] = ILLEGAL_ELEM;
	} else {
		do {
			tmp = curr;
			curr = metadata[curr];
			if (curr == elem) {
				metadata[tmp] = metadata[elem];
				metadata[elem] = ILLEGAL_ELEM;
				break;
			}

		} while ( curr != ILLEGAL_ELEM) ;
	}

 quit:
	return curr;
}





/** Get the next element in the list
 * @param lst  The linked list.
 * @param metadata  Metadata for the list. 
 * @param curr_elem  The element with respect to which, the next
 *                   element is returned.  This element better be a
 *                   member of the list. 
 * @return The element after curr_elem. */
LL_INLINE ll_ind_t LL_next_elem(/*@unused@*/ll_list_t * lst, 
				ll_ind_t metadata[], 
				ll_ind_t curr_elem)
{
	ll_ind_t next_elem;
	(void)lst; /* Not used */
	
	if (curr_elem != ILLEGAL_ELEM) {
		next_elem = metadata[curr_elem];
	} else {
		next_elem = ILLEGAL_ELEM;
	}


	return next_elem;
}















LL_INLINE void LL_add_prio(ll_list_t *lst, ll_ind_t metadata[],
			   ll_ind_t elem, const prior_gt_t pfunc)
{
	ll_ind_t tmp, curr = *lst;
	if (curr == ILLEGAL_ELEM) {
		*lst = elem;
	} else if ( pfunc(elem, curr) )  {
		*lst = elem;
	} else {
		while(1) {
			tmp = curr;
			curr = metadata[curr];
			if (curr == ILLEGAL_ELEM) {
				metadata[tmp] = elem;
				break;
			} else if (  pfunc(elem, curr)) {
				metadata[tmp] = elem;
				break;
			}

		} 

	}

	metadata[elem] = curr;

}


/** Generate a function to add an element to the list in prioritized
 * order. 
 * 
 *  This generates a function that looks like LL_add_prio but with
 * three arguments.  The last arguement in LL_add_prio is substitued
 * with a fixed generation time function name.  The only use for this
 * genrated function is to be able to inline the priority function for
 * increased performance.  Think of this macro as a template generator.
 * @param generated_func The name to be assigned to the generated function.
 * @param pfuncname      The priority function to be used.
 */
#define LL_generator_func( generated_func, pfuncname) 			\
LL_INLINE void generated_func (ll_list_t *lst, ll_ind_t metadata[],	\
			   ll_ind_t elem)				\
{									\
	ll_ind_t tmp, curr = *lst;					\
	if (curr == ILLEGAL_ELEM) { 					\
		*lst = elem;						\
	} else if ( pfuncname(elem, curr) ) {				\
		*lst = elem;						\
	} else {							\
		while(1) {						\
			tmp = curr;					\
			curr = metadata[curr];				\
			if (curr == ILLEGAL_ELEM) {			\
				metadata[tmp] = elem;			\
				break;					\
			} else if (  pfuncname(elem, curr)) {		\
				metadata[tmp] = elem;			\
				break;					\
			}						\
		} 							\
	}								\
	metadata[elem] = curr;						\
}									




/** @} -- End Linked List Functions */






#endif
